package A一周刷爆LeetCode.A基础班.G图;

import java.util.*;

/**
 * @author wei.zhao
 * @description: 最小生成树，K算法
 * @date 2022年03月07日 11:16
 */
public class Code04_Kruskal {

    public static Set<Edge> kruskalMST(Graph graph) {
        // 每个节点所属的集合，只包含自己
        MySets sets = new MySets(graph.nodes.values());
        // 将所有的边放入优先队列中
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparing(a -> a.weight));
        for (Edge edge : graph.edges) {
            priorityQueue.add(edge);
        }
        HashSet<Edge> result = new HashSet<>();
        // 从小到大弹出所有的边
        while (!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll();
            if (!sets.isSameSet(edge.from, edge.to)) {
                // 节点所属的集合不是同一个
                result.add(edge);
                sets.union(edge.from, edge.to);
            }
        }
        return result;
    }


    public static class MySets {

        public HashMap<Node, Set<Node>> map = new HashMap<>();

        public MySets(Collection<Node> nodes) {
            for (Node node : nodes) {
                HashSet<Node> set = new HashSet<>();
                set.add(node);
                map.put(node, set);
            }
        }

        // 判断是否在一个点集中
        public boolean isSameSet(Node node01, Node node02) {
            return map.get(node01) == map.get(node02);
        }

        // 合并点集
        public void union(Node from, Node to) {
            Set<Node> nodesFrom = map.get(from);
            Set<Node> nodesTo = map.get(to);
            for (Node node : nodesFrom) {
                nodesTo.add(node);
                map.put(node, nodesTo);
            }
        }
    }

}
